---
title: "1583. Count Unhappy Friends"
created: 2025-12-16
---
# 1583. Count Unhappy Friends

## 题目 [**1583. Count Unhappy Friends**](https://leetcode.com/problems/count-unhappy-friends/)

![[image-302da67c.png]]

## 思路分析

![[image-e1f7e88e.png]]

因为最后一定会两两配对

猜想：只要不是某个人的首选 就一定不满意

貌似成立

```java
class Solution {
    public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
        // 1. 构建每个人的“首选” 
        // firstChoice[i] 表示 i 最想跟谁在一起
        int[] firstChoice = new int[n];
        for (int i = 0; i < n; i++) {
            firstChoice[i] = preferences[i][0]; // 索引 0 才是最喜欢的
        }

        // 2. 构建实际分配 (pair_true)
        // mate[i] = j 表示 i 当前的对象是 j
        int[] mate = new int[n];
        for (int[] p : pairs) {
            mate[p[0]] = p[1];
            mate[p[1]] = p[0];
        }

        // 3. 比较：如果实际对象 != 首选对象，就算不开心
        int unhappyCount = 0;
        for (int i = 0; i < n; i++) {
            int myActualPartner = mate[i];
            int myDreamPartner = firstChoice[i];

            if (myActualPartner != myDreamPartner) {
                unhappyCount++;
            }
        }
        
        return unhappyCount;
    }
}
```

![[image-0beb9d38.png]]

**但实际上不成立。**

虽然直觉上没得到最好的肯定不爽，但这道题定义的“不开心”是**双向奔赴**的。

假设 **A 的首选是 B**，但 A 被分给了 C。

- **按你的逻辑**：A 不开心（因为没得到 B）。
- **按题目逻辑**：
  - A 确实想找 B。
  - **但是**，如果 B 的当前对象是 D，而且 **B 喜欢 D 胜过喜欢 A**。
  - 这时候，A 虽然想找 B，但 **B 不想理 A**。
  - 在这种情况下，A 只能认命，**不算**题目定义的“不开心朋友”。

题目中“不开心”的条件是：**A 想找 B，而且 B 也觉得 A 比自己现在的对象好**（双方都有出轨意愿），这才叫 Unhappy。

需要判断的不是“是否匹配了首选”，而是“是否存在一个比当前对象更好，且对方也觉得你更好的人”。

## 代码实现

```java
class Solution {
    public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
        // map: 记录每个人的实际配对对象
        // 作用：mate[i] = j 表示 i 和 j 是一对
        int[] mate = new int[n];
        for (int[] p : pairs) {
            mate[p[0]] = p[1];
            mate[p[1]] = p[0];
        }

        // map: 预处理亲密度排名表
        // 作用：rank[i][j] = k 表示：在 i 的心里，j 排在第 k 位（越小越好）
        // 这样我们比较亲密度时，就不需要遍历数组，直接对比整数大小即可
        int[][] rank = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n - 1; k++) {
                int person = preferences[i][k];
                rank[i][person] = k;
            }
        }

        int unhappyCount = 0;

        // 遍历每一个人 x，检查他是否不开心
        for (int x = 0; x < n; x++) {
            int y = mate[x]; // y 是 x 当前的实际对象
            int indexY = rank[x][y]; // y 在 x 心里的排名

            // 核心逻辑：
            // 我们遍历 x 的偏好列表，只看那些 排在 y 前面 的人（即 x 更喜欢的人）
            // 假设 x 更喜欢 u (u 排在 y 前面)
            for (int k = 0; k < indexY; k++) {
                int u = preferences[x][k]; 
                int v = mate[u]; // v 是 u 当前的实际对象
                
                // 此时已知：x 喜欢 u > y
                // 必须检查：u 是否也喜欢 x > v ？
                // 如果是双向奔赴（两边都觉得对方比现任好），那么 x 就是不开心的
                if (rank[u][x] < rank[u][v]) {
                    unhappyCount++;
                    break; // x 已经确定不开心了，不需要再找其他出轨对象了，统计下一个 x
                }
            }
        }

        return unhappyCount;
    }
}
```

假设我们正在判断 **x** 是否不开心：

1. **x 的现状**：跟 **y** 在一起。
2. **x 的心声**：查看 x 的 `preferences` 列表。
   - 如果列表里有一个人 **u**，排在 **y** 前面。
   - 说明：`x 喜欢 u > x 喜欢 y`。
3. **u 的现状**：跟 **v** 在一起。
4. **u 的心声**：利用 `rank` 矩阵快速查看。
   - 如果 `rank[u][x] < rank[u][v]`。
   - 说明：`u 喜欢 x > u 喜欢 v`。
5. **结论**：两人都觉得对方比现任好，**x 是不开心的**（同理 u 也是不开心的，会在 u 的循环里被统计到）。

做不来这么渣的题，，，

## 同类题型

## 视频讲解